package com.paic.du.prob;

import java.util.ArrayList;
import java.util.List;

import com.paic.du.lib.Utils;

//F(i+1,s)=F(i,s)+F(i,s-(i+1)
public class Subset {
	public static int subset(int i, int s) {
		int[][] ans = new int[i + 1][s + 1];
		for (int indexX = 0; indexX <= i; indexX++) {
			for (int indexJ = 0; indexJ <= s; indexJ++) {
				if (indexX == 0)
					ans[indexX][indexJ] = 0;
				else if (indexX != 0 && indexJ == 0)
					ans[indexX][indexJ] = 1;
				else if (indexJ > (indexX * (indexX + 1) / 2))
					ans[indexX][indexJ] = 0;
				else if (indexJ < indexX)
					ans[indexX][indexJ] = ans[indexX - 1][indexJ];
				else
					ans[indexX][indexJ] = ans[indexX - 1][indexJ]
							+ ans[indexX - 1][indexJ - indexX];
				// System.out.println("F("+indexX+","+indexJ+")="+ans[indexX][indexJ]);
			}
		}
		return ans[i][s];
	}

	/*
	 * getAllSubset F(i,j) F(i,j)=(i and F(i-1,j-i)) and F(i-1,j)
	 */

	public static int getSubsetSumOfCal(int i, int j) {
		if (i < Utils.minSum(j))
			return 0;
		return (i - Utils.minSum(j) + 1) + getSubsetSumOfCal(i - 1, j - i);
	}

	public static void printAllCal(int i, int j) {
		if (i < 0 || j < 0)
			return;
		if (j > i * (i + 1) / 2 || 0 == j || 1 == j) {
			// System.out.println("F("+i+","+j+")=0");
			return;
		} else {
			if (j >= i)
				System.out.println("F(" + i + "," + j + ")=F(" + (i - 1) + ","
						+ j + ") + F(" + (i - 1) + "," + (j - i) + ")");
			else
				System.out.println("F(" + i + "," + j + ")=F(" + (i - 1) + ","
						+ j + ")");
			printAllCal(i - 1, j);
			printAllCal(i - 1, j - i);
		}

	}

	public static List<int[]> and(int i, List<int[]> array) {
		int x = 0;

		int size = array.size();

		int[] iRet = new int[1];
		iRet[0] = i;
		List<int[]> ret = new ArrayList<int[]>();
		if (0 == size)
			ret.add(iRet);
		else {
			for (; x < size; x++) {
				int[] m = (int[]) array.get(x);
				int m1[] = new int[m.length + 1];
				for (int tmp = 0; tmp < m.length; tmp++)
					m1[tmp] = m[tmp];
				m1[m.length] = i;
				ret.add(m1);
			}
		}
		return ret;
	}

	public static List<int[]> getAllSubSet(int i, int s) {
		List<int[]> ret = new ArrayList<int[]>();
		if (i < 0 || s <= 0) {
		} else if (1 == s) {
			ret = and(1, ret);
		} else if (i < Utils.minSum(s)) {
		} else if (s < i) {
			ret = getAllSubSet(i - 1, s);
		} else
			ret = and(getAllSubSet(i - 1, s),
					and(i, getAllSubSet(i - 1, s - i)));
		return ret;
	}

	public static void printSebset(List<int[]> a) {
		int len = a.size();
		while (len > 0) {
			int[] item = a.get(len - 1);
			int iLen = item.length;
			System.out.print("[");
			while (iLen > 0) {
				System.out.print(item[iLen - 1]);
				if (1 != iLen)
					System.out.print(", ");
				iLen--;
			}
			System.out.println("]");
			len--;
		}
	}

	public static List<int[]> and(List<int[]> a, List<int[]> b) {
		List<int[]> ret = new ArrayList<int[]>(a.size() + b.size());
		int i = 0;
		int m = b.size();
		while (i<m) {
			ret.add(i, b.get(i));
			i++;
		}
		
		int n = a.size();
		i = 0;
		while (i<n) {
			ret.add(i + m, a.get(i));
			i++;
		}
		return ret;
	}

	public static void main(String[] args) {
		printSebset(getAllSubSet(11, 33));
	}
}
